Lưu An là con trai trưởng của Hoài Nam Lệ vương Lưu Trường, Quốc vương chư hầu thứ hai của nước Hoài Nam. Hoài Nam Lệ vương Lưu Trường là con trai thứ 7 của Hán Cao Tổ Lưu Bang, do đó Lưu An là cháu nội của Hán Cao Tổ, không rõ mẹ ông là ai. Ông chào đời khoảng năm 179 TCN[1].

Lưu Trường vào những năm đầu Hán Văn Đế tỏ ra hống hách ngạo mạn, xem thường thiên tử, cuối cùng bị biếm chức và phải tự tử vào năm 174 TCN. Lưu An khi đó mới 4 tuổi, không còn chỗ nương tựa. Hai năm sau, 172 TCN, Văn Đế thương Hoài Nam vương Trường, bèn phong cho bốn người con của Lưu Trường lên tước hầu, trong đó Lưu An được phong làm Phụ Lăng hầu, ba người em khác là Lưu Bột làm An Dương hầu, Lưu Tứ làm Dương Chu hầu, Lưu Lương làm Đông Thành hầu.